矩阵连乘
代码其实……有点麻烦
详细解读
https://blog.csdn.net/qq_19782019/article/details/94356886
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <iostream>
#include <algorithm>
using namespace std;
int arr[2333];
int m[2333][2333]={0};
int s[2333][2333]={0};
int n;
int main()
{
cin >> n;
for (int i=0;i<=n;i++)
cin >>arr[i];
for (int r=2;r<=n;r++){
for (int i=1;i<=n-r+1;i++){
int j=i+r-1;
m[i][j]=m[i+1][j]+arr[i-1]*arr[i]*arr[j];
s[i][j]=i;
for(int k=i+1;k<j;k++){
int temp=m[i][k]+m[k+i][j]+arr[i-1]*arr[k]*arr[j];
if(m[i][j]>temp)
{
m[i][j]=temp;
s[i][j]=k;
}
}
}
}
cout << m[1][n]<<endl;
return 0;
}
|
举例
A=50*10,B=10*40,C=40*30,D=30*50
|
A |
B |
C |
D |
| A |
0 |
AB 50*10*40 |
A(BC) 27000 |
A(B(CD)) 10500 |
| B |
|
0 |
BC 10*40*30 12000 |
B(CD) 8000 |
| C |
|
|
0 |
CD 40*30*5 6000 |
| D |
|
|
|
0 |
从表格的左上开始，先AB,BC,CD,再[ABC],[BCD],再[ABCD]，中括号[]只是表示矩阵连乘的规模，不是顺序
- m[A][B]=m[B][B]+50*10*40 形成
AB
- m[B][C]=m[C][C]+10*40*30 形成
BC
- m[A][C]=min{ m[A][A]
0 +m[B][C] 12000 +50*10*30 15000 共27000 相当于：A(BC),m[A][B] 20000 +m[C][C] 0 +50*40*30 60000 共80000 相当于：(A)BC}
- m[A][C] 选择两个中小的，形成
A(BC)
……
……
- m[A][D]=min{ m[A][A]
0 +m[B][D] 8000 +50*10*50 25000 共33000 相当于：A[B~D] ,m[A][B] 20000 +m[C][D] 6000 +50*40*50 100000 共126000 相当于：[AB][CD] ,m[A][C] 27000 +m[D][D] 0 +50*30*50 75000 共102000 相当于： [A~C]D }
- 上面的[B~D]其实也会选择最小值，变成B(CD)
- 上面的[A~C]选择最小值，变成A(BC)
- 所以对m[A][D]最小的是
A[B~D]也就是A(B(CD))
三角路径最大
题目
解析
我们不妨将金字塔倒过来
1
2
3
4
5
6
| [
[4,1,8,3],
[6,5,7],
[3,4],
[2]
]
|
我们只要再相邻的元素中选出最大的值，然后往对应的下一层加即可。
例如[4,1,8,3]，4和1比，所以我们将4加到下一层的6。接着，考虑1和8，我们将8加到下一层的5，接着考虑8和3，我们将8加到7，以此类推下去。
基于这个思想我们可以写出这样的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<algorithm>
using namespace std;
int n;
int *the_max;
int arr[1005][1005]={0};
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>arr[i][j];
}
}
the_max=arr[n];
for(int i=n;i>=2;i--){
for(int j=1;j<=i-1;j++){
arr[i-1][j]+=max(arr[i][j],arr[i][j+1]);
}
}
cout<<arr[1][1]<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
|
01背包
题目
野地里有许多不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。要求在规定的时间t里，采到的草药的总价值最大。
- 这里的总时间，就是背包总容量
- 每个草药需要的时间，就是每个物品需要的容量
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int time,herb,tcost[200],hvalue[200];
int f[2000];
int i,j;
int main() {
scanf("%d %d",&time,&herb);
for(i=0;i<herb;i++)
scanf("%d %d",&tcost[i],&hvalue[i]);
for(i=0;i<herb;i++)
for( j=time;j>=tcost[i];j--)
f[j]=max(f[j],f[j-tcost[i]]+hvalue[i]);
printf("%d\n",f[time]);
return 0;
}
|
最长的非连续子序列
题目
在一个数字序列中，找到一个最长的非连续子序列，使得这个子序列是不下降（非递减）。现有序列A={1,2,3,-1,-2,7,9},则A的最长不下降子序列是{1,2,3,7,9}。
如果有多个最长序列，只需选数字顺位靠后的序列从大到小输出。
输入
7
31 96 27 -35 46 -96 0
输出
2
0 -96
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <iostream>
#define themax(a,b) a>b?a:b
using namespace std;
int main() {
int n,res_index;
int arr[105]={0};
int dp[105]={0};
int res_path[1005]={0};
cin>>n;
for(int i=0; i<n; i++) {
cin>>arr[i];
res_path[i]=0;
dp[i]=1;
}
int res=-1;
for(int i=1; i<n; i++) {
for(int j=i-1; j>=0; j--) {
if(arr[i]>=arr[j]){
if(dp[j]+1>dp[i]){
res_path[i]=j;
}
dp[i]=themax(dp[j]+1,dp[i]);
}
}
res=max(res,dp[i]);
}
for(int i=n-1; i>=0; i--) {
if(res==dp[i]) {
res_index=i;
break;
}
}
cout<<res<<endl;
for(int i=n-1; i>=n-res+1; i--) {
cout<<arr[res_index]<<" ";
res_index=res_path[res_index];
}
cout<<arr[res_index]<<endl;
}
|
最长公共子序列
题目与证明
https://blog.csdn.net/weixin_40522938/article/details/111223435
- 当Xm=Yn时，有
- Zk=Xm=Yn，Xm和Yn的LCS等于
X(m-1)和Y(n-1)的LCS，状态1
- 当Xm!=Yn时，有
- Zk!=Xm，Xm和Yn的LCS等于
Xm-1和Yn的LCS，状态2
- Zk!=Yn，Xm和Yn的LCS等于
Xm和Yn-1的LCS，状态3
- 以上两种情况包含了Xm!=Yn时
所有可能的情况，因为所求的LCS必然为以上两种情况中的一种，又因为求的是最长，所以所求LCS = Max(LCS2，LCS3)；
所以LCS的转移方程为
-
c[i][j]=⎩⎪⎪⎨⎪⎪⎧0,c[i−1][j−1]+1,max{c[i][j−1],c[i−1][j]},i> 0 ; j=0i,j>0; Xi=Yji,j>0; Xi!=Yj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
if(x[i]=y[j]){
c[i][j]=c[i-1][j-1]+1;
}
else{
c[i][j]=max(c[i-1][j],c[i][j-1]);
}
if(x[i]=y[j]){
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>c[i][j-1]){
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else{
c[i][j]=c[i][j-1];
b[i][j]=3;
}
void LCS(int i,int j,char *x,int **b){
if(i==0||j==0)
return 0;
if(b[i][j]==1){
LCS(i-1,j-1,x,b);
cout<<x[i];
}
else if(b[i][j]==2){
LCS(i-1,j,x,b);
}else{
LCS(i,j-1,x,b);
}
}
|
最大子段和
子段要求连续
输入 -2,11,-4,13,-5,-2 输出20；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int MaxSum(int n,int *arr){
int theMax=0,b=0;
for(int i=0;i<n;i++){
if(b<=0)
b=arr[i];
else{
b+=arr[i];
}
if(b>theMax)
theMax=b;
}
}
|
